Recently, Gupta et.al. [GKKS2013] proved that over Q any $n^{O(1)}$-variateand $n$-degree polynomial in VP can also be computed by a depth three$\Sigma\Pi\Sigma$ circuit of size $2^{O(\sqrt{n}\log^{3/2}n)}$. Over fixed-sizefinite fields, Grigoriev and Karpinski proved that any $\Sigma\Pi\Sigma$circuit that computes $Det_n$ (or $Perm_n$) must be of size $2^{\Omega(n)}$[GK1998]. In this paper, we prove that over fixed-size finite fields, any$\Sigma\Pi\Sigma$ circuit for computing the iterated matrix multiplicationpolynomial of $n$ generic matrices of size $n\times n$, must be of size$2^{\Omega(n\log n)}$. The importance of this result is that over fixed-sizefields there is no depth reduction technique that can be used to compute allthe $n^{O(1)}$-variate and $n$-degree polynomials in VP by depth 3 circuits ofsize $2^{o(n\log n)}$. The result [GK1998] can only rule out such a possibilityfor depth 3 circuits of size $2^{o(n)}$. We also give an example of an explicit polynomial ($NW_{n,\epsilon}(X)$) inVNP (not known to be in VP), for which any $\Sigma\Pi\Sigma$ circuit computingit (over fixed-size fields) must be of size $2^{\Omega(n\log n)}$. Thepolynomial we consider is constructed from the combinatorial design. Aninteresting feature of this result is that we get the first examples of twopolynomials (one in VP and one in VNP) such that they have provably strongercircuit size lower bounds than Permanent in a reasonably strong model ofcomputation. Next, we prove that any depth 4$\Sigma\Pi^{[O(\sqrt{n})]}\Sigma\Pi^{[\sqrt{n}]}$ circuit computing$NW_{n,\epsilon}(X)$ (over any field) must be of size $2^{\Omega(\sqrt{n}\logn)}$. To the best of our knowledge, the polynomial $NW_{n,\epsilon}(X)$ is thefirst example of an explicit polynomial in VNP such that it requires$2^{\Omega(\sqrt{n}\log n)}$ size depth four circuits, but no known matchingupper bound.
展开▼
